package com.south.base.test.arithmetic;

import java.util.LinkedList;
import java.util.List;

/**
 * 数组形式的整数加法
 * @author Administrator
 * @date 2019/5/27 17:10
 */
public class IntegerArraysAddInteger {
    public static List<Integer> addToArrayForm(int[] a, int k) {
        String kStr = String.valueOf(k);
        int carry = 0;
        // LinkedList速度比ArrayList快的多，ArrayList(92 ms)，LinkedList(11 ms)
        LinkedList<Integer> res = new LinkedList<>();
        for (int i = 1; i <= kStr.length(); i++) {
            int c = Integer.parseInt(String.valueOf(kStr.charAt(kStr.length() - i)));
            int sum = a.length >= i ? c + a[a.length - i] + carry : c + carry;
            res.addFirst(sum % 10);
            carry = sum / 10;
        }
        if (a.length > kStr.length()) {
            for (int i = a.length - kStr.length() - 1; i >= 0; i--) {
                int sum = a[i] + carry;
                res.addFirst(sum % 10);
                carry = sum / 10;
            }
        }
        if (carry == 1) {
            res.addFirst(carry);
        }
        return res;
    }

    public static List<Integer> addToArrayForm2(int[] a, int k) {
        int carry = 0;
        LinkedList<Integer> res = new LinkedList<>();
        for (int i = 1; i <= a.length; i++) {
            int sum = k % 10 + a[a.length - i] + carry;
            res.addFirst(sum % 10);
            carry = sum / 10;
            k /= 10;
        }
        while (k > 0) {
            int sum = k % 10 + carry;
            res.addFirst(sum % 10);
            carry = sum / 10;
            k /= 10;
        }
        if (carry == 1) {
            res.addFirst(carry);
        }
        return res;
    }

    public static void main(String[] args) {
        System.out.println(addToArrayForm(new int[]{9, 9, 9, 9, 9, 9, 9, 9, 9, 9}, 1));
    }
}
